λ¬Έμ
Programmers - κ΄νΈ λ³ν
π Logic
private String recursive(String p) {
// λΉ λ¬Έμμ΄μΈ κ²½μ° λ°ν
if (Objects.equals(p, "")) return p;
// uμ vλ‘ λΆλ¦¬
String[] uv = splitString(p);
String u = uv[0];
String v = uv[1];
// uκ° μ¬λ°λ₯΄λ€λ©΄, vμ λν΄ recurvie()ν κ²°κ³Όλ₯Ό λΆμ¬ λ°ν
if (isProper(u)) return u + recursive(v);
// uκ° μ¬λ°λ₯΄μ§ μμ κ²½μ°
StringBuilder sb = new StringBuilder("(");
sb.append(recursive(v)).append(")").append(reverseBracket(u.substring(1, u.length() - 1)));
return sb.toString();
}
- μ£Όμ΄μ§ "κ· νμ‘ν κ΄νΈ λ¬Έμμ΄"μ "μ¬λ°λ₯Έ κ΄νΈ λ¬Έμμ΄"λ‘ λ³ννλ ν¨μ
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
public String solution(String p) {
// μ΄λ―Έ μ¬λ°λ₯Έ κ²½μ° λ°ν
if (isProper(p)) return p;
// μ¬λ°λ₯΄μ§ μμ κ²½μ°
return recursive(p);
}
private String recursive(String p) {
// λΉ λ¬Έμμ΄μΈ κ²½μ° λ°ν
if (Objects.equals(p, "")) return p;
// uμ vλ‘ λΆλ¦¬
String[] uv = splitString(p);
String u = uv[0];
String v = uv[1];
// uκ° μ¬λ°λ₯΄λ€λ©΄, vμ λν΄ recurvie()ν κ²°κ³Όλ₯Ό λΆμ¬ λ°ν
if (isProper(u)) return u + recursive(v);
// uκ° μ¬λ°λ₯΄μ§ μμ κ²½μ°
StringBuilder sb = new StringBuilder("(");
sb.append(recursive(v)).append(")").append(reverseBracket(u.substring(1, u.length() - 1)));
return sb.toString();
}
// μ¬λ°λ₯Έ κ΄νΈ λ¬Έμμ΄μΈμ§ νμΈνλ ν¨μ, Stack μ¬μ©
private boolean isProper(String p) {
Stack<Character> stack = new Stack<>();
int idx = 0;
while (idx < p.length()) {
char ch = p.charAt(idx);
if (ch == '(')
stack.push(ch);
else
if (stack.size() > 0)
stack.pop();
idx++;
}
return stack.isEmpty();
}
// λΆλ¦¬νλ ν¨μ, (μ κ°μμ )μ κ°μκ° κ°μ κ²½μ°κΉμ§κ° u, λλ¨Έμ§λ v
private String[] splitString(String p) {
String u = "";
String v = "";
int lcount = 0;
int rcount = 0;
int idx = 0;
while(idx < p.length()) {
if (p.charAt(idx) == '(') lcount++;
else rcount++;
idx++;
if (lcount == rcount) {
u = p.substring(0, idx);
v = p.substring(idx);
break;
}
}
return new String[] {u, v};
}
// μ£Όμ΄μ§ λ¬Έμμ΄μ 첫λ²μ§Έμ λ§μ§λ§ λ¬Έμλ₯Ό μ κ±°νκ³ , λλ¨Έμ§ λ¬Έμλ₯Ό λ€μ§λ ν¨μ
private String reverseBracket(String str) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++)
sb.append(str.charAt(i) == '(' ? ")" : "(");
return sb.toString();
}
}
βοΈ Review
- νλΌλ λλ‘λ§ κ΅¬ννλ©΄ μ½κ² ν리λ λ¬Έμ !
- μ΄λ€ ν¨μλ₯Ό νμλ‘ νλμ§ λλμ΄ μκ°νκ³ κ΅¬νν΄λ³΄λ μ°μ΅νκΈ°μ μ’μ λ¬Έμ μλ€.